How AI in Games Works

Lie of the Land

In a similar fashion to Fallout 3 and F.E.A.R. 2, the terrain analysis in Crysis was managed by first triangulating the terrain; after that, the AI can derive a path-finding grid from the triangulation.

Crytek’s Pavel Mores explains that this grid "was unified in the sense that multiple kinds of agents could use it. This was achieved by storing additional data with nodes and links (hints placed by the game designer) to decide, for instance, whether an agent is small enough to pass through a link or whether it can handle the water depth associated with a link".

As well as the terrain triangulation system, Crysis used traditional waypoint graphs to define longitude and latitude on the surface, but it also featured what Mores describes as "specialised support for navigation through 3D space".

He explains that "one part of this is what we call flight navigation, which is effective for volumes where an up-vector can be reasonably defined (where there’s gravitation). The other is volume navigation, which supports free movement in space, so it’s more general at the cost of more complex pre-processing".

Navigating inside 3D volumes is an AI challenge that’s becoming increasingly more important. We aren’t only up against foes on the ground any more; in a game such as F.E.A.R. 2, or even BioShock, we’re now up against mutant beasties that can climb walls and traverse ceilings, as well as hanging off ledges and falling through the air. Monolith uses an impressive method of addressing this in F.E.A.R. 2 with the use of what it calls ‘segments’.


Monolith’s Matt Rice explains that "segments are a series of points and links, which may or may not be on or attached to the navmesh. The AI is free to create paths using these segments just as it would on a normal navmesh". However, unlike a polygon in a navmesh, whereby an AI character is allowed to move to any point within that polygon, a segment is placed in a very specific point in the scene, and these points can be located anywhere in the environment. This, Rice says, gives the "AI characters free rein over the environment, no longer tying them to moving along the floor".

When you combine segments with a planning system, you end up with chaotic scenes in which you can have monsters coming at you from all directions, and in an unpredictable fashion. As an example, Rice says that "while the player is focused on the half-naked Abomination directly in the front, his compatriot will have leapt from the floor to the ceiling directly above, to the wall at the right, and ended up directly behind the player ready to pounce".

Segments are a very complicated feature to implement though. Rice explains that "for the designer, the added complexity of managing all of the segments and links can be daunting". However, he’s confident that "anyone who has battled F.E.A.R. 2’s Abominations will appreciate the many acetaminophen pills the team consumed".

Meanwhile, Relic uses a large number of one-megapixel navigation grids to store the terrain data for the AI in Dawn of War 2. As RTS veterans will know, Company of Heroes introduced the concept of using terrain and objects in the game as various levels of cover, and this continues in Dawn of War 2. To do this, the game needs two grids for cover – one for the terrain, and another for objects and obstacles.

In addition, the game features a grid that describes the largest size of unit that can go into each cell, plus a grid that the units can use to reserve their destinations when moving, so they don’t end up competing with another unit for the same space. On top of that, there’s another grid that describes where units are going to be located in the near future – again to avoid collisions. There’s also a ‘hierarchical sector map’ that describes where cells with identical properties are merged together, which speeds up long-distance searches. That amounts to a total of six maps needed to transport NPCs from A to B in an intelligent fashion.

Relic draws its maps dynamically using rasterisation, just as you would in the 3D world. Relic’s Chris Jurney explains that it’s "just like what a graphics card does when it draws triangles to the screen. When you put a new building into the world, we draw the box that it blocks into the various map grids to update them, exactly like rendering a quad (a group of four pixels) in an overhead view".